1302. Neredeyse Asal Sayılar

 

Neredeyse asal sayılar adece bir tek asal sayı ile bölünebilen asal olmayan sayılardır. Bu problemde göreviniz verilen bir aralık içindeki neredeyse asal sayıların sayısını bulan bir program yazmaktır.

 

Girdi. Girdi dosyasının ilk satırında kaç girdi kümesi bulunduğunu gösteren bir tamsayı n (n ≤ 600) bulunmaktadır. Sonraki n satırın herbirinde tek bir girdi kümesi bulunmaktadır. Her kümede alt ve üst denen iki tamsayı bulunmaktadır (0 < low £ high < 1012).

 

Çıktı. İlk satır dışındaki her bir girdi satırı için bir çıktı satırı üretmelisiniz. Bu çıktı satırında verilen aralıkta (snırlar dahildir) [low.. high]  kaç adet neredeyse asal sayı bulunduğunu gösteren bir tamsayı vardır.

 

Sample input

3
1 10
1 20
1 5

 

Sample output

3
4
1

 

 

ÇÖZÜM

Eratosthenes süzgeci– ikili arama

 

Algoritma analizi

Neredeyse asal sayılar pk şeklindedir, ve burada p asal bir sayı olup, k ³ 2 dir. Neredeyse asal sayıların örnekleri şöyledir, 4, 8, 16, 32, 9, 81, … . high < 1012 olduğu için neredeyse asal sayıların tanumına göre p < 106 olmalıdır. Asal sayıları içeren primes dizisini 1000000 = 106 oluşturun, bu dizide eğer i sayısı asal ise primes[i] = 1 değilse primes[i] = 0 olacaktır. Daha sonra m dizisi içinde bütün neredeyse asal sayıları üretin ve sıralayın (bunların sayısı 80070’e eşittir). f(a, b) ile [a..b] aralığındaki neredeyse asal sayıların adetini gösterelim. Öyleyse f(low, high) = f(1, high) - f(1, low - 1) olur. [1 .. n] aralığındaki neredeyse asal sayıların adeti (index) pozisyonuna eşittir, n‘i sıralı m dizisine üst sınırını kullanarak sıralı düzeni koruyarak yerleştirmek mümkündür. Bu index değeri m dizisi üzerinde ikili arama kullanarak upper_bound fonksiyonuyla bulunabilir.

 

Örnek

1 ile 100 arasındaki bütün neredeyse asal sayıları üretelim. Önce 2‘nin 100’den büyük olmayan üslerini yazın. Sonra sırasıyla 3, 5 ve 7’nin üslerini üretin. 11’in karesi 100’den büyüktür, bu nedenle [1..100] arasında 11’in üsleri yoktur.

Diziyi sıralayın:

İkinci test örneğine bakalım. 1 ile 20 arasında 4 adet neredeyse asal sayı vardır: 4, 8, 9, 16.

 

Algoritma gerçekleştirmesi

primes dizisini asallık testini yapmak için üretin.

 

void gen_primes(void)

{

  int i, j;

  for(i = 0;i < MAX; i++) primes[i] = 1;

  for(i = 2; i <= (int)sqrt(1.0*MAX); i++)

    if (primes[i])

      for(j = i * i; j < MAX; j += i) primes[j] = 0;

}

 

Her bir asal i sayısı için m dizisine i2, i3, i4, …sayılarını 1012 e ulaşana kadar ekleyin. ptr değişkeni m dizisine en son yerleştirilen neredeyse asal sayının indeksini içermektedir. Neredeyse asal sayılar 1012 değeriyle sınırlandığı için sadece 64 bit tamsayıları işlememiz gerekir (long long veri tipi). m dizisinin en sonuna 1012’den büyük herhangi bir sayı koyunuz. Bu sayı 1012 + 1 olsun. Bunun yapılması ikili arama fonksiyonunun doğru çalışması için gereklidir.

 

ptr = -1;

for (i = 2; i < MAX; i++)

  if (primes[i])

  {

    temp = i;

    while ((temp *= i) < 1e12)

      m[++ptr] = temp;

  }

m[++ptr] = 1e12 + 1;

 

m dizisini STL kullanarak sıralayınız:

 

sort(m,m+ptr);

 

Girdi olarak verilecek test durumlarının sayısını n içine okuyun ve her bir [a, b] aralığı için f(a, b) = f(1, b) – f(1, a – 1) değerini sabit zamanda hesaplayarak yazdırınız.

 

scanf("%d",&n);

for(test = 1; test <= n; test++)

{

  scanf("%lld %lld",&a,&b);

  printf("%d\n",upper_bound(m,m+ptr,b) - upper_bound(m,m+ptr,a-1));

}

 

Java gerçekleştirmesi

 

import java.util.*;

 

public class ex

{

  public static ArrayList<Long> primes = new ArrayList<Long>();

 

  public static void GenPrimes()

  {

    final int MAX_SIZE = 1000001;     

    BitSet bits = new BitSet(MAX_SIZE);

 

    bits.set(2, MAX_SIZE, true);

    for (int i = 2; i < Math.sqrt(MAX_SIZE); i++)

    {

      if (bits.get(i))

        for (int j = i * i; j < MAX_SIZE; j += i)

          bits.set(j, false);

    }

   

    for (int i = 2; i < MAX_SIZE; i++)

      if (bits.get(i))

      {

        long temp = i;

        while ((temp *= i) < 1000000000000L)

          primes.add(temp);

      }

    primes.add(1000000000001L);

    Collections.sort(primes);

  }

 

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int tests = con.nextInt();

    GenPrimes();

   

    for(int i = 0; i < tests; i++)

    {

      Long low = con.nextLong();

      Long high = con.nextLong();

      int lIndex = Collections.binarySearch(primes, low);

      if (lIndex < 0) lIndex = -(lIndex + 1);

      int hIndex = Collections.binarySearch(primes, high);

      if (hIndex < 0) hIndex = -(hIndex + 1); else hIndex++;

 

      System.out.println(hIndex - lIndex);

    }

  }

}